Introduction to Machine Learning

Unit 13: Boosting and Adaboost

Introduction

Welcome to Unit 13, where we explore Boosting techniques, with a focus on the AdaBoost algorithm.

Key Concept:

Boosting is an ensemble learning technique that combines multiple weak learners (models that are slightly better than random guessing) to create a strong learner. Unlike bagging (e.g., Random Forest) where models train independently in parallel, boosting builds models sequentially, with each new model focusing on the training examples that previous models struggled with.

This lecture covers:

Theory

How Boosting Works

Boosting operates through a sequential training process with adaptive weighting:

  1. Sequential Training: Models are built one after another
  2. Adaptive Weighting: After each model:
    • ✗ Misclassified instances → Higher weights (more important)
    • ✓ Correctly classified instances → Lower weights (less important)
  3. Learning from Errors: Model \(M_{i+1}\) focuses on training examples that Model \(M_i\) struggled with
  4. Weighted Voting: Final prediction combines all models with weights based on their accuracy

Adaptive Boosting (AdaBoost)

Developed by Freund and Schapire in the 1990s (awarded the prestigious Gödel Prize in 2003), AdaBoost is one of the most influential boosting algorithms.

AdaBoost's Dual Weight System:

  1. Sample Weights (\(w_i\)): Control which training instances each model focuses on
    • Misclassified instances → weights increase
    • Correctly classified instances → weights decrease
    • Each new predictor "pays more attention" to previously misclassified examples
  2. Model Weights (\(\alpha_j\)): Control how much each predictor contributes to final prediction
    • Based on the model's weighted training error (\(\varepsilon\))
    • Lower error → Higher \(\alpha\) → Stronger vote in ensemble
    • Formula: \(\alpha = \frac{1}{2} \ln \left(\frac{1 - \varepsilon}{\varepsilon}\right)\)

The Sequential Process

The AdaBoost algorithm follows this iterative process:

\[ \begin{align*} &1.\ \text{Train } M_1 \rightarrow \text{Calculate error } \varepsilon_1 \rightarrow \text{Determine } \alpha_1 \rightarrow \text{Update sample weights} \\ &2.\ \text{Train } M_2 \rightarrow \text{Calculate error } \varepsilon_2 \rightarrow \text{Determine } \alpha_2 \rightarrow \text{Update sample weights} \\ &3.\ \text{Train } M_3 \rightarrow \text{Calculate error } \varepsilon_3 \rightarrow \text{Determine } \alpha_3 \rightarrow \text{Update sample weights} \\ &\ldots \\ &\text{Final Prediction: } H(x) = \text{sign}\left(\sum \alpha_j \cdot h_j(x)\right) \end{align*} \]

Where:

Building the Weak Learners

In boosting, the ensemble consists of very simple base classifiers, often referred to as weak learners:

  • Typical weak learner: Decision tree stump (decision tree with depth = 1)
  • Key concept: Focus on training examples that are hard to classify
  • Unlike Random Forests (which use bootstrap samples), each weak learner in AdaBoost is trained on the entire dataset
  • After each weak learner is trained, we modify the dataset by enlarging the points that have been incorrectly classified

Log Odds Function

The log-odds function ensures that better classifiers get exponentially more influence than worse ones:

\[ \alpha = \frac{1}{2} \ln \left(\frac{1 - \varepsilon}{\varepsilon}\right) \]

Properties:

Pseudocode for AdaBoost

1. Set the weight vector, w, to uniform weights, where ∑ᵢ wᵢ = 1. 2. For j in m boosting rounds, do the following: a. Train a weighted weak learner: Cⱼ = train(X, y, w). b. Predict class labels: ȳ = predict(Cⱼ, X). c. Compute the weighted error rate: ε = w · (ȳ ≠ y). d. Compute the coefficient: αⱼ = 0.5 log((1 - ε)/ε). e. Update the weights: w ⇐ w × exp(-αⱼ × ȳ × y). f. Normalize the weights to sum to 1: w ⇐ w / ∑ᵢ wᵢ. 3. Compute the final prediction: ȳ = (∑ⱼ₌₁ᵐ(αⱼ × predict(Cⱼ, X)) > 0).

Weight Update Mechanism

The weight update formula is:

\[ w_{\text{new}} = w_{\text{old}} \times \exp(-\alpha_t \times y_i \times h_t(x_i)) \]

Where:

Learning Rate (Shrinkage)

The learning rate, \(\eta \in (0, 1]\), also called shrinkage parameter (default value is 1), controls the magnitude of weight updates:

\[ w_{t+1} = w_t(i) \times \exp(-\eta \cdot \alpha_t \cdot y_i \cdot h_t(x_i)) \]

Where: \(h_t(x_i)\) = prediction of weak learner t on sample i

Bagging vs. Boosting

Aspect Bagging (Random Forest) Boosting (AdaBoost)
Training Parallel (independent models) Sequential (each model depends on previous)
Data Sampling Bootstrap samples (with replacement) Full dataset (with adaptive weights)
Focus Reduces variance Reduces bias
Combining Predictions Simple averaging / majority voting Weighted voting (based on accuracy)
Overfitting Risk Low (due to independence) Medium-High (can overfit to noise)
Typical Accuracy Good Often better (but can be worse if overfit)

Interactive Examples

Example I: Step-by-Step AdaBoost

Let's walk through a concrete example with 10 data points:

Initial Setup:

  1. Add a weight of 1 to every point
  2. Fit a weak learner
  3. Results: Correct: 7, Incorrect: 3
  4. Rescale misclassified points by 7/3
Round 1
Round 2
Round 3

Round 1:

Initial weights: All samples have weight = 1

Weak Learner 1:

  • Accuracy: 7 / 10
  • Error: \(\varepsilon_1 = 3/10 = 0.3\)
  • Score: \(\alpha_1 = \ln(7/3) = 0.847\) (using simplified formula)

Weight Update:

  • Correctly classified (7 samples): \(w_{new} = w_{old} \times \exp(-\alpha_1 \times 1) = 0.064\)
  • Incorrectly classified (3 samples): \(w_{new} = w_{old} \times \exp(-\alpha_1 \times (-1)) = 0.1528\)
  • Normalized: Correct = 0.0714, Incorrect = 0.1667

Round 2:

Rescaled dataset: Misclassified points have higher weights

Weak Learner 2:

  • Sum of correct: 11
  • Sum of incorrect: 3
  • Accuracy: 11 / 14
  • Score: \(\alpha_2 = \ln(11/3) = 1.299\)

Round 3:

Rescaled dataset: Further emphasis on hard examples

Weak Learner 3:

  • Sum of correct: 19
  • Sum of incorrect: 3
  • Accuracy: 19 / 22
  • Score: \(\alpha_3 = \ln(19/3) = 1.846\)

Example II: Visualizing Decision Boundaries

Consider a binary classification problem with triangles (Δ) and circles (O):

AdaBoost Decision Boundaries A four-stage visualization showing initial data distribution, successive decision stumps, increased focus on misclassified points, and the final weighted ensemble prediction. AdaBoost Decision Boundaries Iteratively reweighting difficult observations to build a stronger classifier Initial data distribution BASELINE Majority class is concentrated above the feature threshold. fit weak learner Round 1 · First decision stump WEAK LEARNER 01 A single threshold leaves several triangles misclassified. increase error weights Round 2 · Focus on misclassified points WEAK LEARNER 02 Higher-weight observations receive greater attention in the next stump. combine learners Round 3 · Final ensemble COMBINED MODEL Weighted boundaries produce a more reliable final classification. Majority class Minority class Decision boundary Final prediction: weighted combination of all weak learners

Key Insight: Each subsequent weak learner focuses more on the examples near the classification boundary that previous learners misclassified.

Numerical Solutions

Weight Calculation Example

Let's calculate the weight updates for a concrete dataset:

Index x y Initial Weights Prediction (ŷ) Correct? Updated Weights
11.010.11✓ Yes0.072
22.010.11✓ Yes0.072
33.010.11✓ Yes0.072
44.0-10.1-1✓ Yes0.072
55.0-10.1-1✓ Yes0.072
66.0-10.1-1✓ Yes0.072
77.010.1-1✗ No0.167
88.010.1-1✗ No0.167
99.010.1-1✗ No0.167
1010.0-10.1-1✓ Yes0.072

Step-by-Step Calculation:

Given: \(\alpha_1 = 0.847\) (from Round 1)

For correctly classified samples (7 samples):

  • \(y_i \times h_t(x_i) = +1\)
  • \(w_{new} = w_{old} \times \exp(-\alpha_1 \times 1) = 0.1 \times \exp(-0.847) = 0.064\)

For incorrectly classified samples (3 samples):

  • \(y_i \times h_t(x_i) = -1\)
  • \(w_{new} = w_{old} \times \exp(-\alpha_1 \times (-1)) = 0.1 \times \exp(0.847) = 0.1528\)

Normalization:

  • Sum of new weights = (0.064 × 7) + (0.1528 × 3) = 0.448 + 0.4584 = 0.9064
  • Correct Samples: 0.064 / 0.9064 ≈ 0.0706
  • Incorrect Samples: 0.1528 / 0.9064 ≈ 0.1686

Combining Weak Learners

The final prediction is obtained by weighted voting:

\[ H(x) = \text{sign}\left(\sum_{j=1}^m \alpha_j \cdot h_j(x)\right) \]

Example Calculation:

Ensemble of weak learners forming a strong learner Three weak learners with weighted coefficients feed into a strong learner formula. Weak learner 1 α₁ = 0.847 Weak learner 2 α₂ = 1.299 Weak learner 3 α₃ = 1.846 Strong Learner H(x) = sign(0.847×h₁(x) + 1.299×h₂(x) + 1.846×h₃(x))

Try It Yourself

Problem 1: AdaBoost Weight Calculation

You have a dataset with 8 samples. After training the first weak learner:

  • 5 samples are correctly classified
  • 3 samples are misclassified
  • Initial weights are uniform: \(w_i = 1/8\) for all samples

Tasks:

  1. Calculate the weighted error rate \(\varepsilon_1\)
  2. Calculate the model weight \(\alpha_1\) using \(\alpha = \frac{1}{2} \ln\left(\frac{1-\varepsilon}{\varepsilon}\right)\)
  3. Calculate the new weights for correctly and incorrectly classified samples
  4. Normalize the weights so they sum to 1

Solution:

  1. Weighted error rate: \(\varepsilon_1 = \frac{\text{sum of weights of misclassified}}{\text{sum of all weights}} = \frac{3 \times 1/8}{8 \times 1/8} = 3/8 = 0.375\)
  2. Model weight: \(\alpha_1 = \frac{1}{2} \ln\left(\frac{1-0.375}{0.375}\right) = \frac{1}{2} \ln(1.\overline{6}) \approx \frac{1}{2} \times 0.5108 \approx 0.2554\)
  3. New weights:
    • Correct: \(w_{new} = \frac{1}{8} \times \exp(-0.2554 \times 1) \approx 0.0915\)
    • Incorrect: \(w_{new} = \frac{1}{8} \times \exp(-0.2554 \times (-1)) \approx 0.1326\)
  4. Normalization:
    • Sum = (0.0915 × 5) + (0.1326 × 3) = 0.4575 + 0.3978 = 0.8553
    • Correct: 0.0915 / 0.8553 ≈ 0.1070
    • Incorrect: 0.1326 / 0.8553 ≈ 0.1550
Problem 2: Final Prediction

Given three weak learners with the following predictions for a test sample:

Weak Learner\(\alpha_j\)\(h_j(x)\)
10.5+1
20.8-1
31.2+1

Task: Calculate the final prediction \(H(x)\) using the AdaBoost formula.

Solution:

Using \(H(x) = \text{sign}\left(\sum \alpha_j \cdot h_j(x)\right)\):

= sign(0.5×1 + 0.8×(-1) + 1.2×1)

= sign(0.5 - 0.8 + 1.2)

= sign(0.9)

= +1

Final prediction: +1 (Positive class)

Problem 3: Understanding Weight Updates

Explain why the weight update formula \(w_{new} = w_{old} \times \exp(-\alpha \times y_i \times h_t(x_i))\) increases weights for misclassified samples and decreases weights for correctly classified samples.

Solution:

The weight update formula works as follows:

  • For correctly classified samples: \(y_i \times h_t(x_i) = +1\)
    • \(\exp(-\alpha \times 1) = \exp(-\alpha) < 1\) (since \(\alpha > 0\))
    • Therefore, \(w_{new} = w_{old} \times (\text{something} < 1)\) → weight decreases
  • For misclassified samples: \(y_i \times h_t(x_i) = -1\)
    • \(\exp(-\alpha \times (-1)) = \exp(\alpha) > 1\) (since \(\alpha > 0\))
    • Therefore, \(w_{new} = w_{old} \times (\text{something} > 1)\) → weight increases

Intuition: The formula automatically increases the importance of hard-to-classify samples and reduces the importance of easy samples, forcing subsequent weak learners to focus on the difficult cases.

Interactive Quiz

Test your understanding of Boosting and AdaBoost with these multiple-choice questions:

Question 1: What is the fundamental difference between bagging and boosting?

A) Bagging trains models in parallel, boosting trains models sequentially
B) Bagging uses weak learners, boosting uses strong learners
C) Bagging focuses on misclassified samples, boosting uses random subsets
D) Bagging combines predictions with weighted voting, boosting uses simple averaging

Question 2: In AdaBoost, what happens to the weights of misclassified samples after each iteration?

A) They decrease
B) They increase
C) They remain unchanged
D) They are set to zero

Question 3: What is the typical choice for a weak learner in AdaBoost?

A) Deep neural network
B) Decision tree stump (depth=1)
C) Support Vector Machine
D) k-Nearest Neighbors

Question 4: Which formula correctly calculates the model weight α in AdaBoost?

A) \(\alpha = (1 - \varepsilon) / \varepsilon\)
B) \(\alpha = \frac{1}{2} \ln\left(\frac{1 - \varepsilon}{\varepsilon}\right)\)
C) \(\alpha = \varepsilon / (1 - \varepsilon)\)
D) \(\alpha = \ln(\varepsilon)\)

Question 5: What is the purpose of the learning rate (shrinkage) parameter η in boosting?

A) To increase the number of weak learners
B) To control the magnitude of weight updates
C) To determine the depth of decision trees
D) To select the best features

Key Takeaways

  • Sequential Learning: Boosting builds models one after another, with each new model focusing on the mistakes of previous models.
  • Adaptive Weighting: Misclassified samples get higher weights, forcing subsequent models to pay more attention to difficult cases.
  • Weighted Voting: Final predictions combine all weak learners with weights proportional to their accuracy.
  • Weak Learners: AdaBoost typically uses decision tree stumps (depth=1) as base classifiers.
  • Log-Odds Formula: The model weight \(\alpha = \frac{1}{2} \ln\left(\frac{1-\varepsilon}{\varepsilon}\right)\) ensures better classifiers have exponentially more influence.
  • Weight Update: \(w_{new} = w_{old} \times \exp(-\alpha \times y_i \times h_t(x_i))\) automatically increases weights for misclassified samples.
  • Learning Rate: The \(\eta\) parameter controls weight update magnitude, providing regularization against overfitting.
  • Bagging vs Boosting: Bagging trains models in parallel on bootstrap samples, while boosting trains models sequentially on weighted data.

Common Pitfalls

  • Overfitting: Boosting can overfit the training data, especially with too many weak learners. Use early stopping or learning rate (shrinkage) to prevent this.
  • Noisy Data: Boosting is sensitive to noisy data and outliers. The algorithm will try to fit the noise, which can degrade performance.
  • Choosing k: For decision tree stumps, depth is fixed at 1. Don't confuse this with the number of weak learners (which is a hyperparameter to tune).
  • Weight Initialization: Always initialize weights to sum to 1 (typically \(1/n\) for n samples). Don't forget to normalize after each update.
  • Numerical Stability: When \(\varepsilon = 0\) (perfect classifier), the formula for \(\alpha\) becomes undefined (division by zero). In practice, add a small constant to \(\varepsilon\) to avoid this.
  • Interpretation: Boosting models are often less interpretable than single models. The ensemble nature makes it hard to understand individual predictions.
  • Computational Cost: Boosting can be computationally expensive, especially with many weak learners and large datasets.
  • Class Imbalance: While boosting can handle class imbalance to some extent, extreme imbalance might require additional techniques like oversampling.

Resources

Recommended Reading:

Books:

Practical Implementation: